#include <iostream>
using namespace std;
#define N 5
#define Row 5
#define COLUMN 5
#define ROAD 0
#define WALL 1
#define PASS 2
// 迷宫地图
int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
};
typedef struct
{
    int x;
    int y;
} loc_in_maze;

loc_in_maze path[25];
int path_flag = 0;
int d_x[4] = {0, 1, 0, -1};
int d_y[4] = {1, 0, -1, 0};

void print_path()
{
    cout << "(0,0)";
    for (int i = 0; i < path_flag; i++)
    {
        cout << "->(" << path[i].x << "," << path[i].y << ")";
    }
    cout << endl;
}
void dfs_maze(int loc_x, int loc_y, int maze[Row][COLUMN])
{
    for (int k = 0; k < 4; k++)
    {
        if (loc_x + d_x[k] >= 0 && 
        loc_x + d_x[k] < Row && 
        loc_y + d_y[k] >= 0 && 
        loc_y + d_y[k] < COLUMN && 
        maze[loc_x + d_x[k]][loc_y + d_y[k]] == ROAD)
        {
            maze[loc_x + d_x[k]][loc_y + d_y[k]] == PASS;
            path[path_flag].x = loc_x + d_x[k];
            path[path_flag].y = loc_y + d_y[k];
            path_flag++;
            if (loc_x + d_x[k] == Row - 1 && loc_y + d_y[k] == COLUMN - 1) {
                print_path();
                exit(0);
            }
            else
            {
                dfs_maze(loc_x + d_x[k], loc_y + d_y[k], maze);
            }
            maze[loc_x + d_x[k]][loc_y + d_y[k]] == 0;
            path[path_flag].x = 0;
            path[path_flag].y = 0;
            path_flag--;
        }
    }
}

int main() {
    dfs_maze(0, 0, maze);
    return 0;
}
